/**
 * 
 */
package leetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhongfang
 *
 */
public class AverageofLevelsinBinaryTree {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public static List<Double> averageOfLevels(TreeNode root) {
		List<Double> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new ArrayDeque<>();
		queue.add(root);
		boolean from1 = true;
		while (!queue.isEmpty()) {
			long sum = 0;
			int count = queue.size();
			for (int i = 0; i < count; i++) {
				TreeNode curNode = queue.poll();
				sum += curNode.val;
				if (curNode.left != null) {
					queue.add(curNode.left);
				}
				if (curNode.right != null) {
					queue.add(curNode.right);
				}
			}
			result.add((double) sum / count);
			from1 = !from1;
		}

		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode t1 = new TreeNode(3);
		TreeNode t2 = new TreeNode(9);
		TreeNode t3 = new TreeNode(20);
		TreeNode t4 = new TreeNode(15);
		TreeNode t5 = new TreeNode(7);
		t1.left = t2;
		t1.right = t3;
		t3.left = t4;
		t3.right = t5;
		System.out.println(averageOfLevels(t1));
	}

}
